Provision may typically be made for one or more mobile measurement instruments (for example robots), designed to measure distances between their current position and obstacles in their environment. In what follows, the term “mobile” is understood as meaning a mobile measurement instrument of the aforementioned type. These measurements can for example be performed by measurements of flight time (“LIDAR” teledetection in particular, for “Light Detection and Ranging”), or by any other technique making it possible to measure a distance.
There arises in particular the problem, in real time, referred to as onboard “SLAM” (for “Simultaneous Localization And Mapping”), which consists in having to determine at one and the same time the cartographic mapping and the location of the mobile measurement instrument. Thus, it is necessary to construct a map of the environment of the measurement instrument and at the same time locate this instrument in this map. In practice, these two problems cannot be solved independently. In order for a mobile instrument to be able to establish a map of the environment, the instrument must firstly be in possession of the information relating to the point from where its distance measurements were made. In the same manner, it is difficult to estimate the current position of the instrument without a well-established map. Thus, a good map is necessary in order to self locate, whereas precise estimation of the current position is necessary in order to construct the map.
To describe the objectives aimed at in a more illustrative manner by way of example:                at the input of a mapping system, it is sought to establish the coordinates of the entities to be mapped (walls, doors, furniture, trees, etc.) in the form of points or of clouds of points expressed in a reference frame bound to the mobile instrument, and        at the output of the system, an instantaneous position of the instrument is determined (for example the coordinates X, Y, θ for a plane problem, that is to say for the establishment of a map in 2D),        a sampled map of the environment explored is established therefrom.        
Still by way of illustrative example, in a plane problem, an algorithm updates the map and the position of the instrument (referred to as a “mobile” hereinbelow), in less than 25 ms on an eeePC computer with 1.6 GHz processor clock. The position of the mobile is expressed in the continuous domain, whereas the map is sampled spatially with an interval of 20 mm, for example.
A few SLAM solution methods are currently known.
“Visual SLAM” uses one or more image acquisition systems (generally cameras) and calculates the transformation between two successive images so as to deduce therefrom the displacement of the mobile.
However, these approaches require preprocessing of the video data, which is often hardly compatible with real-time constraints.
The acquisition systems are subject to the lighting conditions, and this may falsify or prevent the location process.
The reconstruction of the map is often difficult on the basis of video images, and one often resorts to a combination with a LIDAR for mapping.
The extraction of “landmarks” consists in extracting from the data of sensors (camera, LIDAR, or other) zones of interest, called “landmarks”, to use them as natural signposts.
However, this is an expensive process, in the same way as image processing.
The extraction possibly being subject to disturbances, this type of approach is generally combined with a stochastic approach (of the type using for example Kalmann filters, as described hereinbelow).
The absence of a landmark in a current field of vision prevents any location.
The approach using Kalmann filters consists in fusing the information originating from several sensors (LIDAR and odometry for example) by using probabilistic models. However, the underlying mathematical models may be complex and they require highly-tuned knowledge of the characteristics of the sensors, in particular the variances in the uncertainty of the measurements. This variance may be difficult to estimate and may also be subject to variations (in particular of the odometric measurements when passing from rough terrain to slippery ground).
The approach using “particle filters” is akin to the so-called Monte Carlo schemes which perform a series of random draws with the final objective of keeping the best.
In practice however, this technique gives poor results if it is not combined with another algorithm.
Depending on the chosen number of particles (on which the quality of the result will depend), compatibility with the real-time constraint is difficult.
Moreover, like any technique using random draws, the results are not reproducible.
The so-called “ICP” (“Iterative Closest Point”) technique consists in associating each LIDAR point with data acquired previously so as to estimate the transformation by a processing of the “least squares” type.
However, the process of matching corresponding points is extremely expensive resource-wise and its complexity is of the order of O(n.log(n)), thereby prohibiting real-time execution in practice.
Furthermore, these schemes are not robust in relation to aberrant data.